/*
 * @lc app=leetcode.cn id=990 lang=cpp
 * @lcpr version=30204
 *
 * [990] 等式方程的可满足性
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class UnionFindSet
{
public:
	UnionFindSet(int n)
	{
		_v.resize(n, -1);
	}

	int FindRoot(int x)
	{
		while (_v[x] >= 0)
		{
			x = _v[x];
		}
		return x;
	}

	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		
		if (root1 == root2)	// x1 x2 在一颗树中
		{
			return false;
		}

		_v[root1] += _v[root2];
		_v[root2] = root1;

		return true;
	}

	size_t Size()
	{
		int n = 0;
		for (auto e : _v)
		{
			if (e < 0)
			{
				++n;
			}
		}
		return n;
	}

private:
	vector<int> _v;
};
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        // 并查集，这题本质是相等的属于同一棵树，不相等的属于不同的树，如果发现不相等的有公共的根就说明冲突了
        UnionFindSet ufs(26);
        // 相等的入集合
        for(auto& str : equations)
        {
            if(str[1] == '=')
            {
                ufs.Union(str[0] - 'a' , str[3]-'a');
            }
        }
        // 不相等的做判断
        for(auto& str : equations)
        {
            if(str[1] == '!')
            {
                if(ufs.FindRoot(str[0]-'a') 
                == ufs.FindRoot(str[3]-'a'))
                {
                    return false;
                }
            }
        }
        return true;
    }
};
// @lc code=end



/*
// @lcpr case=start
// b"\na"]\n
// @lcpr case=end

// @lcpr case=start
// a"\nb"]\n
// @lcpr case=end

// @lcpr case=start
// b"\nc"\nc"]\n
// @lcpr case=end

// @lcpr case=start
// b"\nc"\na"]\n
// @lcpr case=end

// @lcpr case=start
// c"\nd"\nz"]\n
// @lcpr case=end

 */

